home *** CD-ROM | disk | FTP | other *** search
/ AP Professional Graphics CD-ROM Library / AP Professional Graphics CD-ROM Library.iso / pc / unix / appendix / gemsi / seedfill.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-09-15  |  2.4 KB  |  83 lines
  1. /*
  2.  * A Seed Fill Algorithm
  3.  * by Paul Heckbert
  4.  * from "Graphics Gems", Academic Press, 1990
  5.  *
  6.  * user provides pixelread() and pixelwrite() routines
  7.  */
  8.  
  9. /*
  10.  * fill.c : simple seed fill program
  11.  * Calls pixelread() to read pixels, pixelwrite() to write pixels.
  12.  *
  13.  * Paul Heckbert    13 Sept 1982, 28 Jan 1987
  14.  */
  15.  
  16. typedef struct {        /* window: a discrete 2-D rectangle */
  17.     int x0, y0;            /* xmin and ymin */
  18.     int x1, y1;            /* xmax and ymax (inclusive) */
  19. } Window;
  20.  
  21. typedef int Pixel;        /* 1-channel frame buffer assumed */
  22.  
  23. Pixel pixelread();
  24.  
  25. typedef struct {short y, xl, xr, dy;} Segment;
  26. /*
  27.  * Filled horizontal segment of scanline y for xl<=x<=xr.
  28.  * Parent segment was on line y-dy.  dy=1 or -1
  29.  */
  30.  
  31. #define MAX 10000        /* max depth of stack */
  32.  
  33. #define PUSH(Y, XL, XR, DY)    /* push new segment on stack */ \
  34.     if (sp<stack+MAX && Y+(DY)>=win->y0 && Y+(DY)<=win->y1) \
  35.     {sp->y = Y; sp->xl = XL; sp->xr = XR; sp->dy = DY; sp++;}
  36.  
  37. #define POP(Y, XL, XR, DY)    /* pop segment off stack */ \
  38.     {sp--; Y = sp->y+(DY = sp->dy); XL = sp->xl; XR = sp->xr;}
  39.  
  40. /*
  41.  * fill: set the pixel at (x,y) and all of its 4-connected neighbors
  42.  * with the same pixel value to the new pixel value nv.
  43.  * A 4-connected neighbor is a pixel above, below, left, or right of a pixel.
  44.  */
  45.  
  46. fill(x, y, win, nv)
  47. int x, y;    /* seed point */
  48. Window *win;    /* screen window */
  49. Pixel nv;    /* new pixel value */
  50. {
  51.     int l, x1, x2, dy;
  52.     Pixel ov;    /* old pixel value */
  53.     Segment stack[MAX], *sp = stack;    /* stack of filled segments */
  54.  
  55.     ov = pixelread(x, y);        /* read pv at seed point */
  56.     if (ov==nv || x<win->x0 || x>win->x1 || y<win->y0 || y>win->y1) return;
  57.     PUSH(y, x, x, 1);            /* needed in some cases */
  58.     PUSH(y+1, x, x, -1);        /* seed segment (popped 1st) */
  59.  
  60.     while (sp>stack) {
  61.     /* pop segment off stack and fill a neighboring scan line */
  62.     POP(y, x1, x2, dy);
  63.     /*
  64.      * segment of scan line y-dy for x1<=x<=x2 was previously filled,
  65.      * now explore adjacent pixels in scan line y
  66.      */
  67.     for (x=x1; x>=win->x0 && pixelread(x, y)==ov; x--)
  68.         pixelwrite(x, y, nv);
  69.     if (x>=x1) goto skip;
  70.     l = x+1;
  71.     if (l<x1) PUSH(y, l, x1-1, -dy);        /* leak on left? */
  72.     x = x1+1;
  73.     do {
  74.         for (; x<=win->x1 && pixelread(x, y)==ov; x++)
  75.         pixelwrite(x, y, nv);
  76.         PUSH(y, l, x-1, dy);
  77.         if (x>x2+1) PUSH(y, x2+1, x-1, -dy);    /* leak on right? */
  78. skip:        for (x++; x<=x2 && pixelread(x, y)!=ov; x++);
  79.         l = x;
  80.     } while (x<=x2);
  81.     }
  82. }
  83.